package com.fosss.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class CardinalitySort {
    public static void main(String[] args) {
        /*int[] arr = {81, 54, 633, 92, 16, 7,1001};
        System.out.println("排序前数组->"+Arrays.toString(arr));
        cardinalitySort(arr);
        System.out.println("排序后数组->"+Arrays.toString(arr));
*/

        //测试时间复杂度
        //创建一个80000条数据的数组
        int[] arr=new int[80000];
        for(int i = 0; i <80000;i++){
            arr[i]=(int)(Math.random()*80000);
        }
        long startTime = System.currentTimeMillis();
        cardinalitySort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("花费时间"+(endTime-startTime)+"毫秒");//9

    }

    public static void cardinalitySort(int[] arr) {
        //定义一个二维数组，横坐标为桶，纵坐标为桶中存放的数值
        //10个桶，分别代表0-9,因为不知道每个桶中具体会存放几个数，所以将桶的大小设置为数值的个数
        int[][] buckets = new int[10][arr.length];

        //获取最大值，根据最大值的位数来确定进行几次循环
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        //获取最大值的位数
        int maxLength=(max+"").length();


        //按照个位、十位、…… 的顺序分别将其数放到对应的桶中
        //记录桶中放入的元素的个数
        int[] count = new int[10];
        for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                //取出相应的位数上的数字放入对应的桶中
                int number = arr[i] / n % 10;
                //相应位置放入相应的数
                buckets[number][count[number]] = arr[i];
                count[number]++;
            }

            //将桶中的数字依次取出放入到原数组中
            int index = 0;//用来作为arr数组的下标
            for (int i = 0; i < count.length; i++) {
                if (count[i] != 0) {
                    for (int j = 0; j < count[i]; j++) {
                        arr[index] = buckets[i][j];
                        index++;
                    }
                }
                count[i]=0;//!!!!!!!将count 数组清空
            }
//            System.out.println("第"+(k+1)+"轮："+Arrays.toString(arr));
        }
    }
}




















